﻿#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include "h_lz77_old.h"

typedef unsigned char BYTE;
typedef unsigned short UINT16;
typedef unsigned int UINT32;

#define ONCE_IO         2048       /* 每次读写的字节数 */
#define RECENT          32768      /* 最近读入的字节数 */
#define MAX_LINK_LENGTH 32         /* 最长的hash链长度 */
#define HASH_TABLE_SIZE 256        /* hash表大小 */

typedef struct
{
   UINT32 *Offset;
   int Header;
   int Tailer;
} HHashItem;

struct HLz77Global
{
   BYTE *Window;             /* 保存最近读过的数据 */
   UINT32 WindowSize;        /* 窗口缓冲区大小 */
   UINT32 WindowStart;       /* 窗口开始处位于整个文件的位置 */
   UINT32 CurrOffset;        /* 当前处理的数据相对于 */
                             /*     窗口开始的偏移 */
   UINT32 CurrSize;          /* 当前处理的数据大小 */
   int Eof;                  /* 是否已经到文件尾 */
   FILE *fin;
   FILE *fout;
   const char *BufIn;
   char *BufOut;
   int BufInLen;
   int *BufOutLen;
   BYTE *BitsBuf;            /* bits流缓冲区 */
   int BitsBufDataSize;      /* bits流已经读入的数据 */
                             /*   （decompress时）*/
   int BitsBufPointer_byte;  /* bits缓冲区指针 */
   int BitsBufPointer_bit;   /* bits缓冲区指针（字节内）*/
   HHashItem *HashTbl;       /* hash表 */
};

static int CompressInit(HLz77Global &g, FILE *a_fin, FILE *a_fout, const char *a_BufIn, char *a_BufOut, int a_BufInLen, int *a_BufOutLen)
{
   int i;

   if ( a_fin == NULL )
   {
      if ( a_fout != NULL )
      {
         return H_COMPRESS_ERR_OTHER;
      }
      if ( a_BufIn == NULL || a_BufOut == NULL || a_BufInLen == 0 || a_BufOutLen == NULL )
      {
         return H_COMPRESS_ERR_OTHER;
      }
   }
   else
   {
      if ( a_fout == NULL )
      {
         return H_COMPRESS_ERR_OTHER;
      }
      if ( a_BufIn != NULL || a_BufOut != NULL || a_BufInLen != 0 || a_BufOutLen != NULL )
      {
         return H_COMPRESS_ERR_OTHER;
      }
   }

   g.fin = a_fin;
   g.fout = a_fout;
   g.BufIn = a_BufIn;
   g.BufOut = a_BufOut;
   g.BufInLen = a_BufInLen;
   g.BufOutLen = a_BufOutLen;

   if ( g.BufOutLen != NULL )
   {
      *g.BufOutLen = 0;
   }

   g.Window = NULL;
   g.BitsBuf = NULL;
   g.HashTbl = NULL;
   g.WindowSize = RECENT + ONCE_IO * 10;
   g.Window = (BYTE*)malloc(g.WindowSize);

   if ( g.Window == NULL )
   {
      return H_COMPRESS_ERR_NOMEM;
   }

   g.BitsBuf = (BYTE*)malloc(ONCE_IO);

   if ( g.BitsBuf == NULL )
   {
      return H_COMPRESS_ERR_NOMEM;
   }

   g.HashTbl = (HHashItem*)malloc(sizeof(HHashItem) *
      HASH_TABLE_SIZE);

   if ( g.HashTbl == NULL )
   {
      return H_COMPRESS_ERR_NOMEM;
   }

   for ( i = 0; i < HASH_TABLE_SIZE; i++ )
   {
      g.HashTbl[i].Offset = NULL;
   }

   for ( i = 0; i < HASH_TABLE_SIZE; i++ )
   {
      g.HashTbl[i].Offset = (UINT32*)malloc(sizeof(UINT32) *
         MAX_LINK_LENGTH);
      if ( g.HashTbl[i].Offset == NULL )
      {
         return H_COMPRESS_ERR_NOMEM;
      }
      g.HashTbl[i].Header = 0;
      g.HashTbl[i].Tailer = 0;
   }

   g.BitsBufPointer_byte = 0;
   g.BitsBufPointer_bit = 0;
   g.BitsBuf[g.BitsBufPointer_byte] = 0;
   return 0;
}

static void CompressClose(HLz77Global &g)
{
   int i;

   if ( g.HashTbl != NULL )
   {
      for ( i = 0; i < HASH_TABLE_SIZE; i++ )
      {
         if ( g.HashTbl[i].Offset != NULL )
         {
            free(g.HashTbl[i].Offset);
         }
      }
      free(g.HashTbl);
   }

   if ( g.BitsBuf != NULL )
   {
      free(g.BitsBuf);
   }

   if ( g.Window != NULL )
   {
      free(g.Window);
   }
}

static int ReadOnce(HLz77Global &g)
{
   int r;
   int i;
/* 如果剩下的数据量不足 ONCE_IO，再读一块进来。*/
/* 可能引起窗口滑动 */
   if ( g.CurrSize < ONCE_IO && !g.Eof )
   {
      if ( g.CurrOffset + g.CurrSize + ONCE_IO + 500 + 2 > g.WindowSize )
      {
         memmove(g.Window, g.Window + g.CurrOffset - RECENT,
            RECENT + g.CurrSize);
         g.WindowStart += g.CurrOffset - RECENT;
         g.CurrOffset = RECENT;
      }
      for ( i = 0; i < ONCE_IO; )
      {
         if ( g.fin == NULL )
         {
            if ( g.BufInLen > 500 )
            {
               r = 500;
            }
            else
            {
               r = g.BufInLen;
            }
            if ( r > 0 )
            {
               memcpy(g.Window + g.CurrOffset + g.CurrSize, g.BufIn, r);
               g.BufIn += r;
               g.BufInLen -= r;
            }
         }
         else
         {
            r = fread(g.Window + g.CurrOffset + g.CurrSize, 1,
               500, g.fin);
         }
         if ( r <= 0 )
         {
            if ( g.fin == NULL || feof(g.fin) )
            {
               g.Eof = 1;
               break;
            }
            else
            {
               CompressClose(g);
               return H_COMPRESS_ERR_STREAM;
            }
         }
         g.CurrSize += r;
         i += r;
      }
   }

   return 0;
}

static int CompressFlush(HLz77Global &g)
{
   if ( g.BitsBufPointer_bit != 0 )
   {
      g.BitsBuf[g.BitsBufPointer_byte++] <<=
         8 - g.BitsBufPointer_bit;
   }

   if ( g.BitsBufPointer_byte == 0 )
   {
      return 0;
   }

   if ( g.fout == NULL )
   {
      if ( g.BitsBufPointer_byte > 0 )
      {
         memcpy(g.BufOut, g.BitsBuf, g.BitsBufPointer_byte);
         g.BufOut += g.BitsBufPointer_byte;
         *g.BufOutLen += g.BitsBufPointer_byte;
      }
   }
   else
   {
      if ( fwrite(g.BitsBuf, g.BitsBufPointer_byte, 1, g.fout) != 1 )
      {
         return H_COMPRESS_ERR_STREAM;
      }
   }

   return 0;
}

static int PutBits(HLz77Global &g, UINT16 Data, int n)
{
   int k;
   UINT16 i;

   Data <<= 16 - n;

   for ( ; n > 0; )
   {
      k = 8 - g.BitsBufPointer_bit;
      if ( k > n )
      {
         k = n;
      }
      i = g.BitsBuf[g.BitsBufPointer_byte] * 256 + Data / 256;
      i <<= k;
      g.BitsBuf[g.BitsBufPointer_byte] = i / 256;
      Data <<= k;
      n -= k;
      g.BitsBufPointer_bit += k;
      if ( g.BitsBufPointer_bit == 8 )
      {
         g.BitsBufPointer_bit = 0;
         g.BitsBufPointer_byte++;
         if ( g.BitsBufPointer_byte == ONCE_IO )
         {
            if ( g.fout == NULL )
            {
               memcpy(g.BufOut, g.BitsBuf, ONCE_IO);
               g.BufOut += ONCE_IO;
               *g.BufOutLen += ONCE_IO;
            }
            else
            {
               if ( fwrite(g.BitsBuf, ONCE_IO, 1, g.fout) != 1 )
               {
                  return H_COMPRESS_ERR_STREAM;
               }
            }
            g.BitsBufPointer_byte = 0;
         }
         g.BitsBuf[g.BitsBufPointer_byte] = 0;
      }
   }

   return 0;
}

#define COMPRESS_CHECK_ERR \
   if ( r != 0 ) \
   { \
      CompressClose(g); \
      return r; \
   }

static BYTE Hash(const BYTE *Buf)
{
   int i;
   UINT32 Result;

   Result = 0;

   for ( i = 0; i < 3; i++ )
   {
      Result = Result * 5 + *Buf++ + 1;
   }

   return Result % HASH_TABLE_SIZE;
}

static int MatchedLen(BYTE *Str, BYTE *Pattern, int MaxLen)
{
   int r;

   for ( r = 0; r < MaxLen && *Str == *Pattern;
         r++, Str++, Pattern++ )
      ;

   return r;
}

/*
   0  0 -- 7    3
   1  8 -- 23   4
   2 24 -- 55   5
   3 56 -- 255  8
*/

static int PutLength(HLz77Global &g, UINT16 Length)
{
   int r;

   Length -= 3;

   if ( Length < 8 )
   {
      r = PutBits(g, 4, 3);
      if ( r != 0 )
      {
         return r;
      }
      return PutBits(g, Length, 3);
   }

   if ( Length < 24 )
   {
      r = PutBits(g, 5, 3);
      if ( r != 0 )
      {
         return r;
      }
      return PutBits(g, Length - 8, 4);
   }

   if ( Length < 56 )
   {
      r = PutBits(g, 6, 3);
      if ( r != 0 )
      {
         return r;
      }
      return PutBits(g, Length - 24, 5);
   }

   r = PutBits(g, 7, 3);

   if ( r != 0 )
   {
      return r;
   }

   return PutBits(g, Length - 56, 8);
}

/*
   0   0  -- 63    6
   1  64  -- 575   9
   2 576  -- 4671  12
   3 4672 -- 32767 15
*/

static int PutDistance(HLz77Global &g, UINT16 Distance)
{
   int r;

   Distance--;

   if ( Distance < 64 )
   {
      r = PutBits(g, 0, 2);
      if ( r != 0 )
      {
         return r;
      }
      return PutBits(g, Distance, 6);
   }

   if ( Distance < 576 )
   {
      r = PutBits(g, 1, 2);
      if ( r != 0 )
      {
         return r;
      }
      return PutBits(g, Distance - 64, 9);
   }

   if ( Distance < 4672 )
   {
      r = PutBits(g, 2, 2);
      if ( r != 0 )
      {
         return r;
      }
      return PutBits(g, Distance - 576, 12);
   }

   r = PutBits(g, 3, 2);

   if ( r != 0 )
   {
      return r;
   }

   return PutBits(g, Distance - 4672, 15);
}

static void AddHashItem(HLz77Global &g)
{
   int i;
   BYTE Index;
   HHashItem *p;

   if ( g.CurrSize < 3 )
   {
      return;
   }

   Index = Hash(g.Window + g.CurrOffset);
   p = &g.HashTbl[Index];
   p->Header = ( p->Header + 1 ) % MAX_LINK_LENGTH;

   if ( p->Header == p->Tailer )
   {
      p->Tailer = ( p->Tailer + 1 ) % MAX_LINK_LENGTH;
   }

   p->Offset[p->Header] = g.WindowStart + g.CurrOffset;
   return;
}

static int Lz77Compress(FILE *fin, FILE *fout, const char *BufIn, char *BufOut, int BufInLen, int *BufOutLen)
{
   int i, k;
   int Len;
   int r;
   BYTE Index;
   HHashItem *p;
   int Found;
   UINT32 Distance;
   UINT32 FoundOffset;
   int FoundLen;
   HLz77Global g;

   r = CompressInit(g, fin, fout, BufIn, BufOut, BufInLen, BufOutLen);
   COMPRESS_CHECK_ERR;
   g.WindowStart = 0;
   g.CurrOffset = 0;
   g.CurrSize = 0;
   g.Eof = 0;

   for ( ; ; )
   {
      r = ReadOnce(g);
      COMPRESS_CHECK_ERR;
      if ( g.CurrSize == 0 )
      {
         break;
      }
/* 最后剩下的几个字节做常量处理，不压缩 */
      if ( g.CurrSize < 3 )
      {
         r = PutBits(g, g.Window[g.CurrOffset], 9);
         COMPRESS_CHECK_ERR;
         g.CurrOffset++;
         g.CurrSize--;
         continue;
      }
/* 字符串匹配 */
      Index = Hash(g.Window + g.CurrOffset);
      k = g.CurrSize;
      if ( k > 257 )
      {
         k = 257;
      }
      p = &g.HashTbl[Index];
      Found = 0;
      for ( i = p->Header; i != p->Tailer; )
      {
/* 太旧的链截断 */
         Distance = g.WindowStart + g.CurrOffset - p->Offset[i];
         if ( Distance > RECENT )
         {
            p->Tailer = i;
            break;
         }
         if ( Distance + g.CurrSize > k )
         {
            Len = k;
         }
         else
         {
            Len = Distance + g.CurrSize;
         }
         Len = MatchedLen(g.Window + p->Offset[i] - g.WindowStart,
            g.Window + g.CurrOffset, Len);
         if ( Len != 0 )
         {
            if ( !Found )
            {
               FoundOffset = p->Offset[i];
               FoundLen = Len;
               Found = 1;
            }
            else
            {
               if ( Len > FoundLen )
               {
                  FoundOffset = p->Offset[i];
                  FoundLen = Len;
               }
            }
         }
         if ( i == 0 )
         {
            i = MAX_LINK_LENGTH - 1;
         }
         else
         {
            i--;
         }
      }
      if ( !Found || FoundLen < 3 )
      {
         r = PutBits(g, g.Window[g.CurrOffset], 9);
         COMPRESS_CHECK_ERR;
         AddHashItem(g);
         g.CurrOffset++;
         g.CurrSize--;
         continue;
      }
      r = PutLength(g, FoundLen);
      COMPRESS_CHECK_ERR;
      r = PutDistance(g, g.WindowStart + g.CurrOffset - FoundOffset);
      COMPRESS_CHECK_ERR;
      AddHashItem(g);
      g.CurrOffset += FoundLen;
      g.CurrSize -= FoundLen;
   }

   r = PutBits(g, 1, 1);
   COMPRESS_CHECK_ERR;
   r = PutBits(g, 3, 2);
   COMPRESS_CHECK_ERR;
   r = PutBits(g, 258 - 56 - 3, 8);
   COMPRESS_CHECK_ERR;
   r = CompressFlush(g);
   COMPRESS_CHECK_ERR;
   CompressClose(g);
   return 0;
}

static int DecompressInit(HLz77Global &g, FILE *a_fin, FILE *a_fout, const char *a_BufIn, char *a_BufOut, int a_BufInLen, int *a_BufOutLen)
{
   int i;

   if ( a_fin == NULL )
   {
      if ( a_fout != NULL )
      {
         return H_COMPRESS_ERR_OTHER;
      }
      if ( a_BufIn == NULL || a_BufOut == NULL || a_BufInLen == 0 || a_BufOutLen == NULL )
      {
         return H_COMPRESS_ERR_OTHER;
      }
   }
   else
   {
      if ( a_fout == NULL )
      {
         return H_COMPRESS_ERR_OTHER;
      }
      if ( a_BufIn != NULL || a_BufOut != NULL || a_BufInLen != 0 || a_BufOutLen != NULL )
      {
         return H_COMPRESS_ERR_OTHER;
      }
   }

   g.fin = a_fin;
   g.fout = a_fout;
   g.BufIn = a_BufIn;
   g.BufOut = a_BufOut;
   g.BufInLen = a_BufInLen;
   g.BufOutLen = a_BufOutLen;

   if ( g.BufOutLen != NULL )
   {
      *g.BufOutLen = 0;
   }

   g.Window = NULL;
   g.BitsBuf = NULL;
   g.WindowSize = RECENT + ONCE_IO * 10;
   g.Window = (BYTE*)malloc(g.WindowSize);

   if ( g.Window == NULL )
   {
      return H_COMPRESS_ERR_NOMEM;
   }

   g.BitsBuf = (BYTE*)malloc(ONCE_IO);

   if ( g.BitsBuf == NULL )
   {
      return H_COMPRESS_ERR_NOMEM;
   }

   g.BitsBufPointer_byte = 0;
   g.BitsBufPointer_bit = 0;
   g.BitsBufDataSize = 0;
   return 0;
}

static void DecompressClose(HLz77Global &g)
{
   if ( g.BitsBuf != NULL )
   {
      free(g.BitsBuf);
   }

   if ( g.Window != NULL )
   {
      free(g.Window);
   }
}

static int GetBits(HLz77Global &g, UINT16 *Data, int n)
{
   int k;
   UINT16 i, j;

   for ( i = 0; n > 0 ; )
   {
      if ( g.BitsBufPointer_byte == g.BitsBufDataSize )
      {
         if ( g.Eof )
         {
            return H_COMPRESS_ERR_OTHER;
         }
         if ( g.fin == NULL )
         {
            if ( g.BufInLen > ONCE_IO )
            {
               g.BitsBufDataSize = ONCE_IO;
            }
            else
            {
               g.BitsBufDataSize = g.BufInLen;
            }
            if ( g.BitsBufDataSize > 0 )
            {
               memcpy(g.BitsBuf, g.BufIn, g.BitsBufDataSize);
               g.BufIn += g.BitsBufDataSize;
               g.BufInLen -= g.BitsBufDataSize;
            }
         }
         else
         {
            g.BitsBufDataSize = fread(g.BitsBuf, 1, ONCE_IO, g.fin);
         }
         if ( g.BitsBufDataSize < 0 )
         {
            return H_COMPRESS_ERR_STREAM;
         }
         if ( g.BitsBufDataSize < ONCE_IO )
         {
            g.Eof = 1;
         }
         g.BitsBufPointer_byte = 0;
         g.BitsBufPointer_bit = 0;
      }
      k = 8 - g.BitsBufPointer_bit;
      if ( k > n )
      {
         k = n;
      }
      j = ( g.BitsBuf[g.BitsBufPointer_byte] <<
            g.BitsBufPointer_bit ) % 256;
      j <<= k;
      i = ( i << k ) + j / 256;
      n -= k;
      g.BitsBufPointer_bit += k;
      if ( g.BitsBufPointer_bit == 8 )
      {
         g.BitsBufPointer_bit = 0;
         g.BitsBufPointer_byte++;
      }
   }

   *Data = i;
   return 0;
}

static int DecompressOutput(HLz77Global &g, BYTE Data)
{
   g.Window[g.CurrOffset++] = Data;
   g.CurrSize++;

   if ( g.CurrSize == ONCE_IO )
   {
      if ( g.fout == NULL )
      {
         if ( g.CurrSize > 0 )
         {
            memcpy(g.BufOut, g.Window + g.CurrOffset - g.CurrSize, g.CurrSize);
            g.BufOut += g.CurrSize;
            *g.BufOutLen += g.CurrSize;
         }
      }
      else
      {
         if ( fwrite(g.Window + g.CurrOffset - g.CurrSize,
                 g.CurrSize, 1, g.fout) != 1 )
         {
            return H_COMPRESS_ERR_STREAM;
         }
      }
      g.CurrSize = 0;
   }

   if ( g.CurrOffset + ONCE_IO == g.WindowSize )
   {
      memmove(g.Window, g.Window + g.CurrOffset - RECENT, RECENT);
      g.CurrOffset = RECENT;
   }

   return 0;
}

static int DecompressFlush(HLz77Global &g)
{
   if ( g.CurrSize == 0 )
   {
      return 0;
   }

   if ( g.fout == NULL )
   {     
      if ( g.CurrSize > 0 )
      {
         memcpy(g.BufOut, g.Window + g.CurrOffset - g.CurrSize, g.CurrSize);
         g.BufOut += g.CurrSize;
         *g.BufOutLen += g.CurrSize;
      }
   }     
   else  
   {     
      if ( fwrite(g.Window + g.CurrOffset - g.CurrSize,
             g.CurrSize, 1, g.fout) != 1 )
      {
         return H_COMPRESS_ERR_STREAM;
      }
   }

   return 0;
}

static int GetLength(HLz77Global &g, UINT16 *Length)
{
   int r;
   UINT16 i, j;

   r = GetBits(g, &i, 2);

   if ( r != 0 )
   {
      return r;
   }

   switch ( i )
   {
   case 0 :
      r = GetBits(g, &j, 3);
      if ( r != 0 )
      {
         return r;
      }
      *Length = j + 3;
      break;
   case 1 :
      r = GetBits(g, &j, 4);
      if ( r != 0 )
      {
         return r;
      }
      *Length = j + 8 + 3;
      break;
   case 2 :
      r = GetBits(g, &j, 5);
      if ( r != 0 )
      {
         return r;
      }
      *Length = j + 24 + 3;
      break;
   default :
      r = GetBits(g, &j, 8);
      if ( r != 0 )
      {
         return r;
      }
      *Length = j + 56 + 3;
      break;
   }

   return 0;
}

static int GetDistance(HLz77Global &g, UINT16 *Distance)
{
   int r;
   UINT16 i, j;

   r = GetBits(g, &i, 2);

   if ( r != 0 )
   {
      return r;
   }

   switch ( i )
   {
   case 0 :
      r = GetBits(g, &j, 6);
      if ( r != 0 )
      {
         return r;
      }
      *Distance = j + 1;
      break;
   case 1 :
      r = GetBits(g, &j, 9);
      if ( r != 0 )
      {
         return r;
      }
      *Distance = j + 64 + 1;
      break;
   case 2 :
      r = GetBits(g, &j, 12);
      if ( r != 0 )
      {
         return r;
      }
      *Distance = j + 576 + 1;
      break;
   default :
      r = GetBits(g, &j, 15);
      if ( r != 0 )
      {
         return r;
      }
      *Distance = j + 4672 + 1;
      break;
   }

   return 0;
}

#define DECOMPRESS_CHECK_ERR \
   if ( r != 0 ) \
   { \
      DecompressClose(g); \
      return r; \
   }

static int Lz77Decompress(FILE *fin, FILE *fout, const char *BufIn, char *BufOut, int BufInLen, int *BufOutLen)
{
   int r;
   UINT16 i;
   UINT16 Length;
   UINT16 Distance;
   HLz77Global g;

   r = DecompressInit(g, fin, fout, BufIn, BufOut, BufInLen, BufOutLen);
   DECOMPRESS_CHECK_ERR;

   g.CurrOffset = 0;
   g.CurrSize = 0;
   g.Eof = 0;

   for ( ; ; )
   {
      r = GetBits(g, &i, 1);
      DECOMPRESS_CHECK_ERR;
      if ( i == 0 ) /* 常量字符 */
      {
         r = GetBits(g, &i, 8);
         DECOMPRESS_CHECK_ERR;
         r = DecompressOutput(g, i);
         DECOMPRESS_CHECK_ERR;
         continue;
      }
      r = GetLength(g, &Length);
      DECOMPRESS_CHECK_ERR;
      if ( Length == 258 )
      {
         break;
      }
      r = GetDistance(g, &Distance);
      DECOMPRESS_CHECK_ERR;
      if ( Distance > g.CurrOffset )
      {
         return H_COMPRESS_ERR_OTHER;
      }
      for ( i = 0; i < Length; i++ )
      {
         r = DecompressOutput(g, g.Window[g.CurrOffset - Distance]);
         DECOMPRESS_CHECK_ERR;
      }
   }

   r = DecompressFlush(g);
   DECOMPRESS_CHECK_ERR;
   DecompressClose(g);
   return 0;
}

int Lz77CompressFile_old(FILE *fin, FILE *fout)
{
   return Lz77Compress(fin, fout, NULL, NULL, 0, NULL);
}

int Lz77DecompressFile_old(FILE *fin, FILE *fout)
{
   return Lz77Decompress(fin, fout, NULL, NULL, 0, NULL);
}

int Lz77CompressBuf_old(const char *BufIn, char *BufOut, int BufInLen, int *BufOutLen)
{
   return Lz77Compress(NULL, NULL, BufIn, BufOut, BufInLen, BufOutLen);
}

int Lz77DecompressBuf_old(const char *BufIn, char *BufOut, int BufInLen, int *BufOutLen)
{
   return Lz77Decompress(NULL, NULL, BufIn, BufOut, BufInLen, BufOutLen);
}
